package com.company.ljh.easy;
//把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
//
// 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3
//,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
//
// 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2],
//..., a[n-2]] 。
//
//
//
// 示例 1：
//
//
//输入：numbers = [3,4,5,1,2]
//输出：1
//
//
// 示例 2：
//
//
//输入：numbers = [2,2,2,0,1]
//输出：0
//
//
//
//
// 提示：
//
//
// n == numbers.length
// 1 <= n <= 5000
// -5000 <= numbers[i] <= 5000
// numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
//
//
// 注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sor
//ted-array-ii/
// Related Topics 数组 二分查找
// 👍 583 👎 0

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2022/3/29 9:57
 * @version:1.0
 */
public class 旋转数组的最小数字 {
    public int minArray(int[] numbers) {
        int start = 0;
        int end = numbers.length - 1;
        int min = getMin(numbers,start,end);
        return min;
    }

    /**
     * 二分法：
     * 1.取中间数字，对比最右数字和中间数字大小，
     *   大于则舍弃右半数组
     *   小于舍弃左边数组（包括中间数字）
     *   等于舍弃最右边数字（最大时间复杂度O(n)）
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private int getMin(int [] nums,int start,int end){
        int result = 0;
        if (start == end){
            return nums[start];
        }
        int middle = (end - start) / 2 + start;
        if(nums[middle] < nums[end]){
            //舍弃右半部分数据
            result = getMin(nums, start, middle);
        }else if(nums[middle] > nums[end]){
            //舍弃左半部分数据，包括中间数据
            result = getMin(nums,middle + 1,end);
        }else if (nums[middle] == nums[end]){
            result = getMin(nums,start,end - 1);
        }
        return result;
    }
}
